intervals = [[1,3],[2,6],[8,10],[15,18]]
# intervals = [[1,4],[4,5]]
# intervals=[[1,4],[0,4]]
def merge(intervals):
    #对数组进行排序
    # sorted(intervals,key=lambda x:x[0])
    intervals.sort(key=lambda x:x[0])
    print(intervals)
    #一开始在第一个的右边界处
    right_cur=intervals[0][1]
    ans=[]
    ans_index=0
    ans.append([0])
    for i in range(1,len(intervals)):
        if intervals[i][0]<=right_cur:
            #有重叠
            ans[ans_index].append(i)
            right_cur=max(right_cur,intervals[i][1])
        else:
            #没有重叠
            ans.append([i])
            ans_index+=1
            right_cur=intervals[i][1]
    print(ans)
    res=[]
    for i in ans:
        left=intervals[i[0]][0]
        right=0
        for j in i:
            right=max(right,intervals[j][1])
        res.append([left,right])
    print(res)
merge(intervals)